package hero.mps.leet_code_5;

public class LongestPalindrome {
    static boolean isPalindrome(String s, int begin, int end) {
        while(begin <= end)
            if (s.charAt(begin++) != s.charAt(end--)) return false;
        return true;
    }
    public static String longestPalindrome(String s) {
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    if (j -i > right - left) {
                        left = i;
                        right = j;
                    }
                }
            }
        }
        return s.substring(left, right + 1);
    }

    public static String longestPalindrome2(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String res = "";
        int start_0 = 0;
        int end_0 = 0;
        for (int len = 0; len < n; len++) {
            // 遍历所有可能的子串长度
            for (int start = 0; start + len < n; start++) {
                // 计算子串的结束位置
                int end = start + len;
                // 如果子串长度为0，即单个字符，则一定是回文串
                if (len == 0) dp[start][end] = true;
                // 如果子串长度为1，即相邻两个字符，判断它们是否相等
                else if (len ==1) dp[start][end] = s.charAt(start) == s.charAt(end);
                // 如果子串长度大于1，判断首尾字符是否相等，并且去掉首尾的子串是否为回文串
                else dp[start][end] = (s.charAt(start)== s.charAt(end) && dp[start + 1][end - 1]);

                // 如果当前子串是回文串，并且长度大于之前记录的最长回文串长度
                if (dp[start][end] && len + 1 > res.length()) {
                    // 更新最长回文串的起始位置和结束位置
                    start_0 = start;
                    end_0 = end + 1;
                }
            }

        }
        // 根据起始位置和结束位置截取最长回文串并返回
        return s.substring(start_0, end_0);
    }

    public static String longestPalindrome3(String s) {
        // 如果字符串为空或者长度小于1，则返回空字符串
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;

        // 遍历字符串的每个字符
        for (int i = 0; i < s.length(); i++) {
            // 以当前字符为中心，向两边扩展，获取以当前字符为中心的回文子串长度
            int len1 = expandAroundCenter(s, i, i);
            // 以当前字符和下一个字符为中心，向两边扩展，获取以这两个字符为中心的回文子串长度
            int len2 = expandAroundCenter(s, i, i + 1);

            // 取两个回文子串长度的较大值
            int len = Math.max(len1, len2);

            // 如果当前回文子串的长度大于之前的回文子串长度
            if (len > end - start) {
                // 更新回文子串的起始位置
                start = i - (len - 1) / 2;
                // 更新回文子串的结束位置
                end = i + len / 2;
            }
        }

        // 返回最长回文子串
        return s.substring(start, end + 1);
    }

    public static String longestPalindrome4(String s) {
        int len = s.length();
        if (len < 2) return s;
        String str = addBoundaries(s, '#');
        int sLen = 2 * len + 1;
        int maxLen = 1;
        int start = 0;
        for (int i = 0; i < sLen; i++) {
            int curLen = expandAroundCenter(str, i);
            if (curLen > maxLen) {
                maxLen = curLen;
                start = (i - maxLen) / 2;
            }
            
        }
        return s.substring(start, start + maxLen);
    }


    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    private static int expandAroundCenter(String s, int center) {
        int len = s.length();
        int left = center - 1;
        int right = center + 1;
        int step = 0;
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            step++;
        }
        return step;
    }

    private static String addBoundaries(String s, char divide) {
        int len = s.length();
        // 如果字符串长度为0，则返回空字符串
        if (len == 0) return "";
        // 如果字符串中包含分隔符，则抛出异常
        if (s.indexOf(divide) != -1) throw new IllegalArgumentException("String cannot contain the delimiter: " + divide);

        // 创建一个StringBuilder对象用于构建结果字符串
        StringBuilder sb = new StringBuilder();
        // 遍历字符串中的每个字符
        for (int i = 0; i < len; i++) {
            // 在每个字符前添加分隔符
            sb.append(divide);
            // 将当前字符添加到结果字符串中
            sb.append(s.charAt(i));
        }
        // 在结果字符串的末尾添加分隔符
        sb.append(divide);

        // 返回构建好的结果字符串
        return sb.toString();
    }

    public static String longestPalindrome5(String s) {
        int len = s.length();
        if (len < 2) return s;

        // 在字符串s的开头和结尾添加边界字符'#'
        String str = addBoundaries(s, '#');

        // 计算添加边界字符后的字符串长度
        int sLen = 2 * len + 1;

        // 初始化一个数组p，用于保存每个位置的最长回文前缀长度
        int[] p = new int[sLen];

        // 初始化maxRight为0，表示当前最长回文子串的右边界
        int maxRight = 0;

        // 初始化center为0，表示当前最长回文子串的中心位置
        int center = 0;

        // 初始化maxLen为1，表示最长回文子串的长度至少为1
        int maxLen = 1;

        // 初始化start为0，表示最长回文子串在原始字符串s中的起始位置
        int start = 0;

        for (int i = 0; i < sLen; i++) {
            // 如果当前位置i在maxRight的左侧
            if (i < maxRight) {
                // 计算i关于center的对称位置mirror
                int mirror = 2 * center - i;
                // p[i]取maxRight - i和p[mirror]的较小值
                p[i] = Math.min(maxRight - i, p[mirror]);
            }

            // 计算当前位置i的左边界和右边界
            int left = i - (1 + p[i]);
            int right = i + (1 + p[i]);

            // 不断尝试扩展左右边界，直到左右边界的字符不相等或超出字符串范围
            while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
                p[i]++;
                left--;
                right++;
            }

            // 如果当前位置i的右边界超过了maxRight
            if (i + p[i] > maxRight) {
                // 更新maxRight和center的值
                maxRight = i + p[i];
                center = i;
            }

            // 如果当前位置i的最长回文前缀长度超过了maxLen
            if (p[i] > maxLen) {
                // 更新maxLen和start的值
                maxLen = p[i];
                start = (i - maxLen) / 2;
            }
        }

        // 返回最长回文子串
        return s.substring(start, start + maxLen);
    }
    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome5(s));
    }

}
